Task:

Given an undirected or a directed graph, find a path or circuit that passes through each edge exactly once.

Solution:

First let's see the conditions for an undirected graph:

• An undirected graph has an eulerian circuit if and only if it is connected and each vertex has an even degree (degree is the number of edges that are adjacent to that vertex).
• An undirected graph has an eulerian path if and only if it is connected and all vertices except 2 have even degree. One of those 2 vertices that have an odd degree must be the start vertex, and the other one must be the end vertex.

• A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree.
• A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex).

Algorithm for undirected graphs:

1. Start with an empty stack and an empty circuit (eulerian path).
   - If all vertices have even degree - choose any of them.
   - If there are exactly 2 vertices having an odd degree - choose one of them.
   - Otherwise no euler circuit or path exists.
   
2. If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.
   
3. Repeat step 2 until the current vertex has no more neighbors and the stack is empty.


Note that obtained circuit will be in reverse order - from end vertex to start vertex.

1. Start with an empty stack and an empty circuit (eulerian path).
   - If all vertices have same out-degrees as in-degrees - choose any of them.
   - If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - then choose the vertex that has its out-degree with one greater than its in-degree.
   - Otherwise no euler circuit or path exists.
   
2. If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
   
3. Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.


Note that obtained circuit will be in reverse order - from end vertex to start vertex.

Given: A sample undirected graph made in Graph Magics. Below execution steps of this algorithm are shown (all images are created in Graph Magics).
Legend: - current vertex is surrounded by red color Starting state: Stack: empty Location: none Circuit: empty	Download this graph (viewable with Graph Magics)
Because all vertices have even degrees, we can select any vertex as start point. Let it be 1. Current state: Stack: empty Location: 1 Circuit: empty
Go to vertex 2 (a neighbor of 1), add 1 to the stack, delete the edge between 1 and 2. Current state: Stack: 1 Location: 2 Circuit: empty
Go to vertex 3, add 2 to the stack, delete the edge between 2 and 3. Current state: Stack: 1, 2 Location: 3 Circuit: empty
Go to vertex 4, add 3 to the stack, delete the edge between 3 and 4. Current state: Stack: 1, 2, 3 Location: 4 Circuit: empty
Go to vertex 2, add 4 to the stack, delete the edge between 4 and 2. Current state: Stack: 1, 2, 3, 4 Location: 2 Circuit: empty
Go to vertex 8, add 2 to the stack, delete the edge between 2 and 8. Current state: Stack: 1, 2, 3, 4, 2 Location: 8 Circuit: empty
Go to vertex 1, add 8 to the stack, delete the edge between 8 and 1. Current state: Stack: 1, 2, 3, 4, 2, 8 Location: 1 Circuit: empty
Go to vertex 6, add 1 to the stack, delete the edge between 1 and 6. Current state: Stack: 1, 2, 3, 4, 2, 8, 1 Location: 6 Circuit: empty
Go to vertex 9, add 6 to the stack, delete the edge between 6 and 9. Current state: Stack: 1, 2, 3, 4, 2, 8, 1, 6 Location: 9 Circuit: empty
Go to vertex 1, add 9 to the stack, delete the edge between 9 and 1. Current state: Stack: 1, 2, 3, 4, 2, 8, 1, 6, 9 Location: 1 Circuit: empty
Because vertex 1 (current location) has no more neighbors left - we add it to the circuit, take the vertex from the top of the stack (i.e. vertex 9), and set it as the current location. Current state: Stack: 1, 2, 3, 4, 2, 8, 1, 6 Location: 9 Circuit: 1
Vertex 9 has no neighbors left. Thus we add it to the end of the circuit, remove vertex 6 from the stack and set it as the current location. Current state: Stack: 1, 2, 3, 4, 2, 8, 1 Location: 6 Circuit: 1, 9
Vertex 6 has no nieghbors left. Add it to the circuit, remove 1 from the stack and set it as the current location. Current state: Stack: 1, 2, 3, 4, 2, 8 Location: 1 Circuit: 1, 9, 6
Add 1 to the circuit, go to vertex 8 and remove it from the sack. Current state: Stack: 1, 2, 3, 4, 2 Location: 8 Circuit: 1, 9, 6, 1
Now 8 has still some more neighbors left. We take one of them - let it be 5. Add 8 to the stack, go to vertex 5 and delete the edge between these two vertices. Current state: Stack: 1, 2, 3, 4, 2, 8 Location: 5 Circuit: 1, 9, 6, 1
Go to vertex 7, add 5 to the stack and delete the edge between these two vertices. Current state: Stack: 1, 2, 3, 4, 2, 8, 5 Location: 7 Circuit: 1, 9, 6, 1
Go to vertex 8, add 7 to the stack and delete the edge between these two vertices. Current state: Stack: 1, 2, 3, 4, 2, 8, 5, 7 Location: 8 Circuit: 1, 9, 6, 1
Note that no more edges are left, so next steps will only take last vertex from the stack and will add it to the circuit. Add 8 to the circuit, return to vertex 7 and remove it from the stack. Current state: Stack: 1, 2, 3, 4, 2, 8, 5 Location: 7 Circuit: 1, 9, 6, 1, 8
Add 7 to the circuit, return to 5 and remove it from the stack. Current state: Stack: 1, 2, 3, 4, 2, 8 Location: 5 Circuit: 1, 9, 6, 1, 8, 7
Add 5 to the circuit, return to 8 and remove it from the stack. Current state: Stack: 1, 2, 3, 4, 2 Location: 8 Circuit: 1, 9, 6, 1, 8, 7, 5
Add 8 to the circuit, return to 2 and remove it from the stack. Current state: Stack: 1, 2, 3, 4 Location: 2 Circuit: 1, 9, 6, 1, 8, 7, 5, 8
Add 2 to the circuit, return to 4 and remove it from the stack. Current state: Stack: 1, 2, 3 Location: 4 Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2
Add 4 to the circuit, return to 3 and remove it from the stack. Current state: Stack: 1, 2 Location: 3 Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4
Add 3 to the circuit, return to 2 and remove it from the stack. Current state: Stack: 1 Location: 2 Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3
Add 2 to the circuit, return to 1 and remove it from the stack. Current state: Stack: Location: 1 Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3, 2
The stack is empty and 1 has no more neighbors. So this is the last point in this eulerian tour. Finally add 1 to the circuit. Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3, 2, 1 Here the order doesn't matter, but for directed graphs - it's crucial. So let's consider the Eulerian Tour for this graph to be the reverse of the above circuit: 1, 2, 3, 4, 2, 8, 5, 7, 8, 1, 6, 9, 1